/* 
 * File:   quicksort.h
 * Author: Jonas Delrue
 *
 * Created on March 15, 2010, 11:50 AM
 */
#include  <vector>
#ifndef _QUICKSORT_H
#define	_QUICKSORT_H

void quicksort( vector<int> & v, int l, int r){
    if(l<r){
        //v[l] als spil
        int pivot=v[l];
        int i=l, j=r;

        while (v[j] > pivot)
            j--;
        while(i<j){
            int h= v[i]; v[i] = v[j]; v[j] = h;
            i++;
            while(v[i] < pivot)
                i++;
            j--;
            while(v[j] > pivot){
                j--;
            }
        }
        quicksort(v,l,j);
        quicksort(v,j+1,r);
        
    }
}
void startquicksort(vector<int> &v){
    quicksort(v,0,v.size()-1);
}



void quicksortRandom( vector<int> & v, int l, int r){
    if(l<r){
        //rand spil
        srand((unsigned)time(0));

       
         //max--; //dont include the last number in result (definition of "between")
        int range = (l - r) + 1;
         int pivot=l  + int((double)range * rand() / (double)(RAND_MAX + 1.0));


        int i=l, j=r;

        while (v[j] > pivot)
            j--;
        while(i<j){
            int h= v[i]; v[i] = v[j]; v[j] = h;
            i++;
            while(v[i] < pivot)
                i++;
            j--;
            while(v[j] > pivot){
                j--;
            }
        }
        quicksortRandom(v,l,j);
        quicksortRandom(v,j+1,r);

    }


}
        void startquicksortRandom(vector<int> &v){
    quicksortRandom(v,0,v.size()-1);
}

#endif	/* _QUICKSORT_H */

